package com.ashin.dp;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Author: Ashin
 * @Date: 2020/9/28
 * @Description: com.ashin.dp
 * @Version: 1.0.0
 */
public class Package {


    @Test
    public void test001Package() {
        int[][] good = {{3, 5}, {2, 2}, {1, 3}};
        int pack = pack(5, good);
        System.out.print(pack);
    }


    public void packGreedyValue(int capacity, int[][] good) {

        for (int rowIdx = 0; rowIdx < good.length; rowIdx++) {

        }
    }

    public int pack(int capacity, int[][] good) {
        if (capacity == 0 || good.length == 0) {
            return 0;
        }

        int maxVal = 0;
        for (int i = 0; i < good.length; i++) {
            if (good[i][0] > capacity) {
                //放不下，换下一个物品
                continue;
            }
            // good 移除已经放入包中的物品
            int weight = good[i][0];
            int value = good[i][1];
            int[][] newGood = copyGood(good, i);
            int v1 = value + pack(capacity - weight, newGood);


            maxVal = Math.max(Math.max(v1, 0), maxVal);
        }


        return maxVal;
    }

    @Test
    public void test001copyGood() {
        int[][] array = {{1, 2}, {3, 4}};
        int[][] ints = copyGood(array, 0);
        System.out.println(Arrays.toString(ints[0]));
    }

    private int[][] copyGood(int[][] good, int i) {
        int[][] newGood = new int[good.length - 1][2];
        for (int goodIdx = 0; goodIdx < good.length; goodIdx++) {
            if (goodIdx == i) {
                continue;
            }
            if (goodIdx > i) {
                newGood[goodIdx - 1][0] = good[goodIdx][0];
                newGood[goodIdx - 1][1] = good[goodIdx][1];

            } else {
                newGood[goodIdx][0] = good[goodIdx][0];
                newGood[goodIdx][1] = good[goodIdx][1];
            }
        }

        return newGood;
    }

    @Test
    public void solveDP() {
        // 物品的总数，背包能容纳的总重量
        int N = 6, W = 12;
//        // 物品的重量
//        int[] w = {0, 3, 2, 1};
//        // 物品的价值
//        int[] v = {0, 5, 2, 3};

        // 物品的重量
        int[] w = {0, 1, 2, 1, 7, 9, 4};
        // 物品的价值
        int[] v = {0, 1, 2, 1, 7, 9, 4};
        // 输出答案
        System.out.println(dp(w, v, N, W));
    }

    private int dp(int[] w, int[] v, int N, int W) {
        // 创建备忘录 dp[n][w]表示有物品n个背包为w的最大价值
        //背包容量还剩 rw 时，放入前 tn 种物品时的最大价值
        int[][] dp = new int[N + 1][W + 1];

        // 遍历每一件物品
        for (int tn = 1; tn < N + 1; tn++) {
            // 背包容量有多大就还要计算多少次
            System.out.println(String.format("第%d件物品,重量为%d,价值%d", tn, w[tn], v[tn]));
            for (int rw = 1; rw < W + 1; rw++) {
                if (rw < w[tn]) {
                    // 当背包容量小于第tn件物品重量时，只能放入前tn-1件

                    dp[tn][rw] = dp[tn - 1][rw];
                    System.out.println(String.format("dp[%d][%d]=%d,当背包容量小于第tn件物品重量时，只能放入前tn-1件物品价值%d", tn, rw, dp[tn][rw], dp[tn - 1][rw]));
                } else {
                    // 当背包容量还大于第tn件物品重量时，进一步作出决策
                    dp[tn][rw] = Math.max(dp[tn - 1][rw], dp[tn - 1][rw - w[tn]] + v[tn]);
                    System.out.println(String.format("dp[%d][%d]=%d", tn, rw, dp[tn][rw]));
                }
            }
        }

        return dp[N][W];
    }


}
